ARC057 B - 高橋君ゲーム - 競プロ

ARC057 B - 高橋君ゲーム

https://atcoder.jp/contests/arc057/tasks/arc057_b

解答

code: python

n, k = map(int, input().split())

INF = 10**18

# dpi := i日機嫌が良い場合のk(ゲームに勝つ回数)の最小値

dp = INF * (n+1)

dp0 = 0

# ゲームをした回数

cnt = 0

for i in range(n):

# ゲームをする回数

a = int(input())

if i == 0:

dp1 = 1

else:

for j in range(n, 0, -1):

num = dpj-1 * (cnt + a) // cnt + 1

if num - dpj-1 <= a:

dpj = min(dpj, num)

cnt += a

if cnt == k:

print(1)

exit()

for i in range(n,- 1, -1):

if dpi <= k:

print(i)

exit()

code: python

n, k = map(int, input().split())

a = int(input()) for _ in range(n)

INF = int(1e9) + 7

games = 0 * (n+1)

for i in range(n):

gamesi + 1 = gamesi + ai

# print(games)

# 0, 2, 5, 12, 16, 25

# 全ゲーム全勝

if gamesn == k:

print(1)

exit()

# dpij := i 日目までに j 回機嫌が良くなるようにするために必要な最低限の勝ち数

dp = [INF for _ in range(n+1) for _ in range(n+1)]

dp00 = 0

for i in range(n):

for j in range(i + 1):

if dpij < INF:

# i 日目は機嫌を良くしないとすると全敗するのが最適

dpi + 1j = min(dpi + 1j, dpij)

# i 日目を機嫌よくするとすると最低限勝つのが最適

if i == 0:

dpi + 1j + 1 = min(dpi + 1j + 1, dpij + 1)

else:

# 最低限の算出???

atleast = (dpij * gamesi + 1 // gamesi) + 1

dpi + 1j + 1 = min(dpi + 1j + 1, atleast)

# print(dp)

# 0, 1000000007, 1000000007, 1000000007, 1000000007, 1000000007], 0, 1, 1000000007, 1000000007, 1000000007, 1000000007, 0, 1, 3, 1000000007, 1000000007, 1000000007, 0, 1, 3, 8, 1000000007, 1000000007, 0, 1, 2, 5, 11, 1000000007, [0, 1, 2, 4, 8, 18

for i in range(n, -1, -1):

# 「k 回勝った」というのは「k 回以下勝った」と言い換えても同じ

if dpni <= k:

print(i)

break

テーマ

蟻本 2-3 01ナップサック問題その2

メモ

AtCoder Regular Contest 057 B - 高橋君ゲーム

https://img.atcoder.jp/data/arc/057/editorial.pdf

提出

code: python

n, k = map(int, input().split())

a = int(input()) for _ in range(n)

game_count = []

res = 0

for v in a:

res += v

game_count.append(res)

# print(game_count)

# 2, 5, 12, 16, 25

# print(1/2, 3/5, 4/12, 7/16, 7/25)

# 0.5, 0.6, 0.3333333333333333, 0.4375, 0.28

# k をいつ使うか